package priv.solution;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class Solution44CubeCount {

    public static void main(String[] args) {
//        for (int i = 81; i < 82; i++) {
        int i = 1000000-1;
        System.out.println("i=" + i + ",solution=" + solution("" + i));
        System.out.println("i=" + i + ",solution=" + solution1("" + i));
//        }
    }

    private static String solution1(String line) {
        if (line == null || line.equals("")) {
            return "";
        }
        int n = Integer.parseInt(line.trim());

        if (n < 8) {
            return Integer.toString(n);
        }
        if (n < 16) {
            return Integer.toString(n % 8 + 1);
        }

        int steps = 0;
        int minSteps = n;
        int len = (int) Math.pow(n, 1.0 / 3) + 1;
        int[] cubes = new int[len];
        int[] count = new int[len];

        for (int i = 0; i < len; i++) {
            cubes[i] = (len - i) * (len - i) * (len - i);
        }

        boolean back = false;
        int index = 0;
        while (index >= 0) {

            if (!back) {
                if (steps >= minSteps) {
                    index--;
                    back = true;
                    continue;
                }
                if (n < 8) {
                    int tmp = steps + n;
                    if (tmp < minSteps) {
                        minSteps = tmp;
                    }
                    index--;
                    back = true;
                    continue;
                }
                int x = n / cubes[index];
                int y = n % cubes[index];
                if (x == 0) {
                    index++;
                    back = false;
                    continue;
                }
                if (y == 0) {
                    int tmp = steps + x;
                    if (tmp < minSteps) {
                        minSteps = tmp;
                    }
                    index--;
                    back = true;
                    continue;
                }
                count[index] = x;
                steps += x;
                n = y;
                index++;
                continue;
            } else {
                if (count[index] == 0) {
                    index--;
                    back = true;
                    continue;
                } else {
                    count[index]--;
                    n += cubes[index];
                    steps--;
                    index++;
                    back = false;
                }
            }
        }//end while
        return Integer.toString(minSteps);
    }

    private static String solution(String line) {
        if (line == null || line.equals("")) {
            return "";
        }

        int[] cubes = {1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096, 4913, 5832, 6859, 8000, 9261, 10648, 12167, 13824, 15625, 17576, 19683, 21952, 24389, 27000, 29791, 32768, 35937, 39304, 42875, 46656, 50653, 54872, 59319, 64000, 68921, 74088, 79507, 85184, 91125, 97336, 103823, 110592, 117649, 125000, 132651, 140608, 148877, 157464, 166375, 175616, 185193, 195112, 205379, 216000, 226981, 238328, 250047, 262144, 274625, 287496, 300763, 314432, 328509, 343000, 357911, 373248, 389017, 405224, 421875, 438976, 456533, 474552, 493039, 512000, 531441, 551368, 571787, 592704, 614125, 636056, 658503, 681472, 704969, 729000, 753571, 778688, 804357, 830584, 857375, 884736, 912673, 941192, 970299};

        int n = Integer.parseInt(line.trim());
        ArrayList<Integer> queue = new ArrayList<>();
        Set<Integer> reached = new HashSet<>();
        queue.add(n);
        int steps = 0;

        int i = 0;


        while (i < queue.size()) {
            int len = queue.size();
            while (i < len) {
                Integer value = queue.get(i);
                int maxIndex = (int) Math.pow(value, 1.0 / 3);
                for (int j = 0; j < maxIndex; j++) {
                    int next = value - cubes[j];
                    if (next == 0) {
                        return Integer.toString(steps);
                    }
                    if (!reached.contains(next)) {
                        queue.add(next);
                        reached.add(next);
                    }
                }
                i++;
            }
            steps++;
        }
        return "";
    }
}